package com.lft.doublelinkedlist2;

/**
 *
 */
public class DoubleLinkedListDemo {
	public static void main(String[] args) {
		DoubleLinkedList list = new DoubleLinkedList();
		// 头插
		list.insertFirst(new Node(1));
		list.insertFirst(new Node(2));
		list.insertFirst(new Node(3));
		// 尾插
		list.insertLast(new Node(4));
		list.insertLast(new Node(5));
		list.insertLast(new Node(6));
		// 任意插
		System.out.println("是否插入成功 " + list.insertAfter(new Node(7), 3));
		
		// 从前往后遍历
		list.displayForward();
		// 从后往前遍历
		list.displayBackward();
		
		// 删除
		System.out.println("从前面删除");
		list.deleteFirst();
		list.displayForward();
		System.out.println("从后面删除");
		list.deleteLast();
		list.displayForward();
		System.out.println("从中间删除 4");
		list.deleteKey(4);
		list.displayForward();
		
	}
}

class DoubleLinkedList {
	private Node first;
	private Node last;
	
	public DoubleLinkedList() {
		this.first = null;
		this.last = null;
	}
	
	/**
	 * 判断链表是否为空。
	 * @return boolean
	 */
	public boolean isEmpty() {
		return first == null;
	}
	
	/**
	 * 从头部插入
	 * @param node 要插入的节点
	 */
	public void insertFirst(Node node) {
		if (isEmpty()) {
			last = node;
		} else {
			this.first.setPre(node);
		}
		node.setNext(this.first);
		this.first = node;
	}
	
	/**
	 * 从尾部插入
	 * @param node 要插入的节点
	 */
	public void insertLast(Node node) {
		if (isEmpty()) {
			this.first = node;
		} else {
			this.last.setNext(node);
			node.setPre(last);
		}
		last = node;
	}
	
	/**
	 * 将节点插入到指定数据结点的后面
	 * @param node  要插入的节点
	 * @param value 指定插入在哪个节点值后面
	 * @return 插入成功返回 true,插入失败返回 false
	 */
	public boolean insertAfter(Node node, int value) {
		Node curNode = this.first;
		while (curNode != null && curNode.getData() != value) {
			curNode = curNode.getNext();
		}
		if (curNode == null) {
			return false;
		}
		if (curNode == this.last) {
			last = node;
		} else {
			node.setNext(curNode.getNext());
			curNode.getNext().setPre(node);
		}
		node.setPre(curNode);
		curNode.setNext(node);
		return true;
	}
	
	/**
	 * 从头部删除一个节点
	 * @return 返回删除的节点
	 */
	public Node deleteFirst() {
		Node temp = this.first;
		if (this.first.getNext() == null) {
			// 说明只有一个节点。
			last = null;
		} else {
			this.first.getNext().setPre(null);
		}
		this.first = this.first.getNext();
		return temp;
	}
	
	/**
	 * 从尾部删除一个节点
	 * @return 返回删除的节点
	 */
	public Node deleteLast() {
		Node temp = this.last;
		if (this.first.getNext() == null) {
			this.first = null;
		} else {
			this.last.getPre().setNext(null);
		}
		this.last = this.last.getPre();
		return temp;
	}
	
	public Node deleteKey(int value) {
		Node curNode = this.first;
		while (curNode != null && curNode.getData() != value) {
			curNode = curNode.getNext();
		}
		if (curNode == null) {
			return null;
		}
		if (this.first == curNode) {
			this.first = curNode.getNext();
		} else {
			curNode.getPre().setNext(curNode.getNext());
		}
		if (curNode == this.last) {
			this.last = curNode.getPre();
		} else {
			curNode.getNext().setPre(curNode.getPre());
		}
		return curNode;
	}
	
	/**
	 * 从前向后遍历
	 */
	public void displayForward() {
		System.out.println("First --> Last");
		Node curNode = this.first;
		while (curNode != null) {
			curNode.displayLinkedList();
			curNode = curNode.getNext();
		}
		System.out.println();
	}
	
	/**
	 * 从后向前遍历
	 */
	public void displayBackward() {
		System.out.println("Last --> First");
		Node curNode = this.last;
		while (curNode != null) {
			curNode.displayLinkedList();
			curNode = curNode.getPre();
		}
		System.out.println();
	}
	
}

class Node {
	private int data;
	private Node pre;
	private Node next;
	
	public Node(int data) {
		this.data = data;
	}
	
	public int getData() {
		return data;
	}
	
	public void setData(int data) {
		this.data = data;
	}
	
	public Node getPre() {
		return pre;
	}
	
	public void setPre(Node pre) {
		this.pre = pre;
	}
	
	public Node getNext() {
		return next;
	}
	
	public void setNext(Node next) {
		this.next = next;
	}
	
	public void displayLinkedList() {
		System.out.print(this.data + " <-> ");
	}
	
	@Override
	public String toString() {
		return "Node{" +
				"data=" + data +
				'}';
	}
}